package com.study.data.structure.linkedlist;

/**
 * 单链表
 *
 * @author YangGuGu
 */
public class MyLinkedList<T extends Comparable<T>> {

  /**
   * 初始化dummy节点
   */
  private final LinkedNode<T> dummy = new LinkedNode<>();
  /**
   * 初始化 tail 节点
   */
  private LinkedNode<T> tail = dummy;
  /**
   * 链表的长度
   */
  private int length = 0;

  /**
   * 向链表头部添加一个值为 value 的节点
   *
   * @param value
   *     待添加节点的值
   */
  public void addToHead(T value) {
    // 创建新节点
    LinkedNode<T> headNode = new LinkedNode<>(value);
    // 设置新节点的下个节点为 dummy 节点的下个节点
    headNode.setNext(dummy.getNext());
    // 如果当前 dummy 节点和 tail 节点相等，则需要重置 tail 节点指向新节点，即此时新节点为tail节点。
    if (dummy == tail) {
      tail = headNode;
    }
    // 设置 dummy 节点的下个节点为新节点
    dummy.setNext(headNode);
    // 链表长度加 1
    length++;
  }

  /**
   * 向链表尾部添加一个值为 value 的节点
   *
   * @param value
   *     待添加节点的值，不允许为 null
   */
  public void addToTail(T value) {
    // 设置 tail 的下个节点为 value 对应的节点
    tail.setNext(new LinkedNode<>(value));
    // 设置 tail 指向最后一个节点
    tail = tail.getNext();
    // 链表长度加 1
    length++;
  }

  /**
   * 添加节点到指定位置
   *
   * @param index
   *     指定位置
   * @param value
   *     节点的值
   */
  public void addAtIndex(int index, T value) {
    if (index > length) {
      return;
    }
    if (index <= 0) {
      // 往头部添加
      addToHead(value);
    } else if (index == length) {
      // 往尾部添加
      addToTail(value);
    } else {
      // 获取 index 的上个节点
      LinkedNode<T> preNode = getPreNode(index);
      // 创建新节点
      LinkedNode<T> node = new LinkedNode<>(value);
      // 设置节点关联关系
      node.setNext(preNode.getNext());
      preNode.setNext(node);
      // 链表长度加1
      length++;
    }
  }

  /**
   * 删除下标 index 对应的节点
   *
   * @param index
   *     下标
   */
  public void deleteAtIndex(int index) {
    // 下标不合法，直接返回
    if (index < 0 || index >= length) {
      return;
    }
    // 获取指定下标 index 的上个节点
    LinkedNode<T> preNode = getPreNode(index);
    //
    if (tail == preNode.getNext()) {
      tail = preNode;
    }
    preNode.setNext(preNode.getNext().getNext());
    length--;
  }

  /**
   * 获取指定下标 index 的节点值，如果未找到或者下标范围不合法，返回 null
   *
   * @param index
   *     下标
   * @return 下标 index 的节点值
   */
  public T get(int index) {
    if (index < 0 || index > length) {
      return null;
    }
    LinkedNode<T> node = getPreNode(index).getNext();
    if (node == null) {
      return null;
    }
    return node.getValue();
  }

  /**
   * 获取指定下标 index 节点的上个节点，如果未找到或者空链表则返回 dummy 节点
   *
   * @param index
   *     下标
   * @return 下标 index 的上个节点
   */
  private LinkedNode<T> getPreNode(int index) {
    // index 范围不合法，返回 dummy 节点
    if (index < 0 || index > length) {
      return dummy;
    }
    // 空链表，返回 dummy 节点
    if (isEmpty()) {
      return dummy;
    }
    // 一前一后，一块往前走
    LinkedNode<T> front = dummy.getNext();
    LinkedNode<T> back = dummy;
    for (int i = 0; i < index && front != null; i++) {
      back = front;
      front = front.getNext();
    }
    return back;
  }

  /**
   * 链表长度
   */
  public int getLength() {
    return length;
  }

  /**
   * 是否是空链表
   */
  public boolean isEmpty() {
    return getLength() == 0;
  }

  public void print() {
    LinkedNode<T> next = dummy.getNext();
    StringBuilder sb = new StringBuilder();
    while (next != null) {
      sb.append(next.toString());

      next = next.getNext();
      if (next != null) {
        sb.append("->");
      }
    }
    System.out.println(sb.toString());

    System.out.println("tail节点：" + tail.getValue().toString());
  }
}
